package lc20240521;

public class Demo1 {
    public static void main(String[] args) {

        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.left.left=new TreeNode(4);
        root.right=new TreeNode(3);
        flatten(root);
        System.out.println(root.right.right.val);
    }
    public static void flatten(TreeNode root){
        flattenTree(root);
    }
    public static TreeNode flattenTree(TreeNode node) {
        if (node == null) {
            return null;
        }

        // Recursively flatten the left and right subtrees
        //左右尾巴节点。主要是断链，接链。
        TreeNode leftTail = flattenTree(node.left);
        TreeNode rightTail = flattenTree(node.right);

        // If there was a left subtree, we shuffle the connections around
        if (leftTail != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }

        // Return the "tail" of the flattened tree rooted at this node
        //返回尾巴节点
        return rightTail != null ? rightTail : (leftTail != null ? leftTail : node);
    }
}
